package _05_树.tree;
import java.util.Comparator;

/*
    ◼ 红黑树必须满足以下 5 条性质
    1. 节点是 RED 或者 BLACK
    2. 根节点是 BLACK
    3. 叶子节点（外部节点，空节点）都是 BLACK
    4. RED 节点的子节点都是 BLACK
    ✓ RED 节点的 parent 都是 BLACK
    ✓ 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点
    5. 从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点

    建议新添加的叶子节点默认为红色，能更快的满足上述性质中的1 2 3 5

    ◼ 红黑树 和 4阶B树（2-3-4树）具有等价性
    ◼ BLACK 节点与它的 RED 子节点融合在一起，形成1个B树节点
    ◼ 红黑树的 BLACK 节点个数 与 4阶B树的节点总个数 相等
    ◼ 网上有些教程：用 2-3树 与 红黑树 进行类比，这是极其不严谨的，2-3树 并不能完美匹配 红黑树 的所有情况
 */
public class RBTree<E> extends BBST<E>{
    //红黑树颜色节点的定义 红为假  黑为真
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    public RBTree(){
        this(null);
    }

    public RBTree(Comparator<E> comparator){
        super(comparator);
    }

    //红黑树的节点类
    private static class RBNode<E> extends Node<E>{
        boolean color = RED; //节点的颜色
        public RBNode(){
            this(null,null);
        }
        public RBNode(E element,Node<E> parent){
            super(element, parent);
        }
        @Override
        public String toString() {
            String str = "";
            if(color == RED){
                str = "R_";
            }
            return str+element.toString();
        }
    }

    /**
     * RBTree添加节点，共有12种情况，默认新添加的节点颜色为红色
     * 1.4种新添加的节点父节点为黑色，满足红黑树的5条性质，不处理
     * 2.4种不上溢的情况，但是父节点是红色(双红)，有LL/RR,LR/RL，判定条件是叔父节点不是红色
     *   对于LL/RR的情况，要对祖父节点进行左旋转或者右旋转，同时将父节点染成黑色，祖父节点染成红色
     *   对于LR/RL的情况，要对父节点进行左旋转或右旋转，在对祖父节点进行左旋转或者右旋转，将待添加节点染成黑色，祖父节点染成红色
     * 3.4种添加后产生上溢的情况，判定条件是叔父节点是红色；
     *   这时，将父节点和叔父节点染成黑色节点，各自分裂，将祖父节点染成红色向上合并，当成一个新添加的节点进行递归处理
     *   可能向上合并后，还会产生上溢现象，会持续到根节点，所以到达根节点将其染成黑色即可
     *
     * @param node 新添加的节点
     */
    @Override
    protected void afterAdd(Node<E> node) {
        Node<E> parent = node.parent;
        //添加的是根节点或者上溢到达了根节点，直接染成黑色返回即可
        if(parent == null){
            black(node);
            return;
        }

        //情况1 父节点是黑色
        if(isBlack(parent)) return;

        //拿到叔父节点，根据判定条件
        Node<E> uncle = parent.sibling();
        //祖父节点
        Node<E> grand = parent.parent;

        //情况3 叔父节点是红色 上溢
        if(isRed(uncle)){
            black(parent);
            black(uncle);
            afterAdd(red(grand)); //递归处理
            return;
        }

        //情况2 叔父节点不是红色 旋转
        if(parent.isLeftChild()){
            red(grand);
            if(node.isLeftChild()){ //LL
                black(parent);
            }else{ //LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        }else{
            red(grand);
            if(node.isLeftChild()){ //RL
                black(node);
                rotateRight(parent);
            }else{ //RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }

    /**
     *
     * @param node 待删除的节点或用于取代的节点
     *
     */
    @Override
    protected void afterRemove(Node<E> node) {
        //1.删除红色节点，直接删除即可 两个可以融合
        //2.删除黑色节点
        //1.删除有两个红色子节点的黑色节点，这种情况不用考虑，最终删除的是叶子节点
        //2.删除有一个红色子节点的黑色节点
        //用于取代的子节点是红色，将其染黑即可
        if(isRed(node)){
            black(node);
            return;
        }

        //删除的是根节点
        Node<E> parent = node.parent;
        if(parent == null) return;

        //删除黑色叶子节点
        //需要找到兄弟节点，但是兄弟节点在之前的删除逻辑中父节点的那根线已经断了，无法通过node.sibling()找到兄弟节点
        //逆向思维 判断被删除的节点在左还是右
        boolean left = parent.left == null || node.isLeftChild(); //下溢后产生的下溢现象，可以用第二个条件判断
        Node<E> sibling = left ? parent.right : parent.left;

        if(left){ //被删除的节点在左边 兄弟节点在右边
            //删除的节点在左边和删除的节点在右边逻辑完全一样，只是方向相反
            if(isRed(sibling)){
                black(sibling);
                red(parent);
                rotateLeft(parent);
                sibling = parent.right;
            }
            if(isBlack(sibling.left) && isBlack(sibling.right)){
                //没有，借不了
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                if(parentBlack){ //父节点是黑色的情况，导致父节点也会下溢
                    afterRemove(parent);
                }
            }else{
                //有至少一个，可以借
                if(isBlack(sibling.right)){
                    rotateRight(sibling);
                    sibling = parent.right; //旋转以后 兄弟节点也变了
                }
                color(sibling,colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }

        }else{ //被删除的在右边 兄弟节点在左边

            //先考虑兄弟节点是红色的情况，将其转成兄弟节点为黑色的情况,下面就能统一处理
            if(isRed(sibling)){
                black(sibling);
                red(parent);
                rotateRight(parent);
                sibling = parent.left;
            }

            //其次考虑兄弟节点是黑色的情况
            //看兄弟节点是否有一个红色的子节点可以借
            if(isBlack(sibling.left) && isBlack(sibling.right)){
                //没有，借不了
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if(parentBlack){ //父节点是黑色的情况，导致父节点也会下溢
                    afterRemove(parent);
                }
            }else{
                //有至少一个，可以借
                //先处理需要双旋的情况，兄弟节点的左节点是黑色，将兄弟节点左旋转，后面即可统一处理
                if(isBlack(sibling.left)){
                    rotateLeft(sibling);
                    sibling = parent.left; //旋转以后 兄弟节点也变了
                }
                //统一对父节点进行右旋转,再将中心节点染成和父节点一样的颜色，左右节点染成黑色
                //中心节点其实也就是兄弟节点
                color(sibling,colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }

    /**
     * 对节点染色的方法
     * @param node 待染色的节点
     * @param color 颜色
     * @return 返回染色后的节点
     */
    private Node<E> color(Node<E> node,boolean color){
        if(node == null) return null;
        ((RBNode<E>)node).color = color;
        return node;
    }

    /**
     * 将节点染成红色
     * @param node 带染色的节点
     * @return 返回染成红色的节点
     */
    private Node<E> red(Node<E> node){
        return color(node,RED);
    }

    /**
     * 将节点染成黑色
     * @param node 带染色的节点
     * @return 返回染成黑色的节点
     */
    private Node<E> black(Node<E> node){
        return color(node,BLACK);
    }

    /**
     * 判断节点颜色的方法
     * @param node
     * @return 返回节点的颜色
     */
    private boolean colorOf(Node<E> node){
        return node == null ? BLACK : ((RBNode<E>)node).color;
    }

    //判断节点颜色是否是红色
    private boolean isRed(Node<E> node){
        return colorOf(node) == RED;
    }

    //判断节点颜色是否是黑色
    private boolean isBlack(Node<E> node){
        return colorOf(node) == BLACK;
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RBNode<>(element,parent);
    }
}
